package tree.leetcode_437_medium_backtrace;

import java.util.HashMap;
import java.util.Map;

public class BestSolution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(-2);
        root.right = new TreeNode(-3);
        new BestSolution().pathSum(root, -1);
    }
    /**
     * @param root 根节点
     * @param sum  目标值
     * @return 符合目标值的路径数
     */
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> prefixSum = new HashMap<>();
        //前缀和为0的路径，出现了1次。
        prefixSum.put(0, 1);
        return recursionPathSum(root, sum, prefixSum, 0);
    }

    public int recursionPathSum(TreeNode root, int target, Map<Integer, Integer> prefixSum, int curSum) {
        //1. 递归终止条件
        if (root == null) {
            return 0;
        }
        //2. 每一层递归要做的事
        //记录符合条件的路径，初始值为0
        int res = 0;

        //记录当前节点的路径和
        curSum += root.val;
        /**
         * getOrDefault(Object Key, V defaultValue)：返回指定Key的映射，如果不存在则返回默认值 V defaultValue
         *
         * 如果curSum - target的值是之前存在的路径和，
         * 说明 路径和为curSum - target的节点 到 路径和为curSum节点 之间存在一条路径 的和满足target
         */
        res += prefixSum.getOrDefault(curSum - target, 0);

        //更新路径上当前节点的curSum的个数，没出现过的就添加进去。
        prefixSum.put(curSum, prefixSum.getOrDefault(curSum, 0) + 1);

        res += recursionPathSum(root.left, target, prefixSum, curSum);
        res += recursionPathSum(root.right, target, prefixSum, curSum);
        //回溯，去掉当前递归，该层节点的前缀和数量（引用类型，不删除会造成分支污染，比如：如果另一层递归出现的curSum之前也出现过，那么将会记录出现了两次）
        prefixSum.put(curSum,prefixSum.get(curSum) - 1);
        return res;
    }
}
